package com.lxl.merge;

import sun.applet.Main;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Classname AntiOrder
 * @Description 将归并的从小到大排序 换成 从大到小排序
 *
 * @Date 2021/8/16 9:43
 * @Created by LXLDEMO
 */
public class AntiOrder {

    // 记录逆序对信息
    private static Map<String,Object> antiOrderMap = new HashMap<>();

    public static void main(String[] args) {
        // 测试数据
        int[] arr = {2,4,3,1,6,5};
        antiOrder(arr);
    }


    /**
     * 求逆序对
     * @param arr
     */
    public static void antiOrder(int[] arr){
        if (arr == null || arr.length<2){
            System.out.println("逆序对的数量为 0");
            return;
        }

        int[] temp = new int[arr.length];
        int minsum = mergeSort4AntiOrder(arr,temp,0,arr.length-1);

        System.out.println("逆序对的数量为  "+minsum);
        System.out.println("逆序对如下：");
        System.out.println(antiOrderMap.toString());
        antiOrderMap = new HashMap<>();
    }


    /**
     * 求逆序对
     * @param arr
     * @param temp
     * @param start
     * @param end
     * @return
     */
    public static int mergeSort4AntiOrder(int[] arr,int[] temp,int start,int end){
        if (start >= end){
            return 0;
        }
        int mid = (start + end) / 2;

        // 排序第一个数组 计算第一个数组中逆序对
        int leftAnti = mergeSort4AntiOrder(arr,temp,start,mid);
        // 排序第二个数组 计算第二个数组中逆序对
        int rughtAnti = mergeSort4AntiOrder(arr,temp,mid+1,end);
        // 合并两个有序数组 计算总的数组中逆序对
        int allAnti = merge4AntiOrder(arr,temp,start,mid,end);

        return leftAnti + rughtAnti +allAnti;
    }

    /**
     * 求逆序对
     * @param arr   存放两个有序列表的数组
     * @param temp  临时数组
     * @param start 左侧有序列表开始的下标
     * @param mid   左侧结束位置下标  右侧开始位置下标：mid+1
     * @param end   右侧有序列表结束下标
     * @return 本组小和
     */
    public static int merge4AntiOrder(int[] arr,int[] temp,int start,int mid,int end){
        System.out.println("前一组开始下标 "+start);
        System.out.println("前一组结束下标 "+mid);
        System.out.println("后一组开始下标 "+(mid+1));
        System.out.println("后一组结束下标 "+end);
        int i = start; // i 用来记录 第一个数组的遍历位置
        int j = mid + 1; // 用来记录第二个数组的遍历位置
        int k = start; // 用来表示临时数组的下标
        int antiResult = 0;
        // i=mid+1:第一个数组先遍历完成
        // j=end+1:第二个数组先遍历完成
        while (i != mid +1 && j != end +1){
            if (arr[i]<arr[j]){
                temp[k++] = arr[j++];
            }else {

                // 统计逆序对
                if (arr[i]>arr[j]){
                    antiResult += end-j+1; // 计算逆序对数量
                    // 逆序对内容
                    for (int index = j;index<=end;index++){
                        antiOrderMap.put(antiOrderMap.size()==0?"1":(antiOrderMap.size()+1)+"","("+arr[i]+","+arr[index]+")");

                    }
                }


                temp[k++] = arr[i++];
            }
        }
        // 第一个数组没有遍历完毕
        while (i != mid + 1){
            temp[k++] = arr[i++];
        }

        // 第二个元素没有遍历完毕
        while (j != end + 1){
            temp[k++] = arr[j++];
        }

        for (int n = start;n<=end;n++){
            arr[n] = temp[n];
        }
        System.out.println("本次合并结果："+ Arrays.toString(arr));
        return antiResult;
    }
}
